\subsection{An $O(\min\{n^{1.5}\sqrt{\log n}, nk\})$ round algorithm}
\label{sec:upper}
Our algorithm is given in Algorithm~\ref{alg:flow_based} and analyzed
in Lemma~\ref{lem:level.flow} and~\ref{thm:flow_based}, whose proofs
are deferred to the appendix due to space constraints.

\begin{lemma}
\label{lem:level.flow}
Let there be $k \leq n$ tokens at given source nodes and let $v$ be an
arbitrary node. Then, all the tokens can be sent to $v$ using
broadcasts in $O(n)$ rounds.
\end{lemma}

\begin{algorithm}[ht!]
\caption{$O(\min\{n^{1.5} \sqrt{\log n}, nk\})$ round algorithm in the
  offline model}
\label{alg:flow_based}
\begin{algorithmic}[1]
%  \REQUIRE A sequence of communication graphs $G_i$, $i = 1, 2, \ldots$
%  \ENSURE Schedule to disseminate $k$ tokens.
%  \medskip
  \IF{$k \leq \sqrt{n \log n}$}

  \FOR{each token $t$} \label{alg.step:flow_based.trivial}

  \STATE For the next $n$ rounds, let every node who has token
  $t$ broadcast the token.

  \ENDFOR 

  \ELSE

  \STATE Choose a set $S$ of $\sqrt{n \log n}$ random nodes.
  
  \FOR{each vertex in $v \in S$} \label{alg.step:flow_based.phase_1}

  \STATE Send each of the $k$ tokens to vertex $v$ in $O(n)$ rounds. 

  \ENDFOR

  \FOR{each token $t$} \label{alg.step:flow_based.phase_2}

  \STATE For the next $\sqrt{n \log n}$ rounds, let every node who has token
  $t$ broadcast the token.

  \ENDFOR

  \ENDIF

\end{algorithmic}
\end{algorithm}

\begin{theorem}
\label{thm:flow_based}
Algorithm~\ref{alg:flow_based} solves the $k$-gossip problem using
$O(\min\{n^{1.5} \sqrt{\log n}, nk\})$ rounds with high probability in
the offline model.
\end{theorem}
Algorithm~\ref{alg:flow_based} can be derandomized using the standard
technique of conditional expectations.  We defer the proof of this
claim to the full paper.
